package digui;

public class _011逆序对 {
    public static void main(String[] args) {
        /*int[] a = {2,4,6,8};
        int[] b = {1,3,5,7};
        int[] solve = solve(a, b);
        for (int i = 0 ; i < solve.length ;i++){
            System.out.print(solve[i] + " ");
        }*/
        int[] arr =utils.Utils.getRandomArr(10,1,20);
        for (int i = 0 ; i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        sort(arr);
        for (int i = 0; i <arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("niXu" + niXu);
    }

    //合并有序数组
    //给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B，编写一个方法，将B融入A
    //快排思想
    public static int[] solve(int[] a,int[] b){
        int n = a.length;
        int m = b.length;
        int totalLength = m + n;
        int[] total = new int[m+n];
        System.arraycopy(a,0,total,0,n);
        System.arraycopy(b,0,total,n,m);
        quickSort(total,0,total.length-1);
        return total;
    }

     public static void quickSort(int[] a,int p,int r){
        if (p<r){
            int q = partition(a,p,r);
            quickSort(a,p,q-1);
            quickSort(a,q+1,r);
        }
    }

    public static int partition(int[] a,int p ,int r){
        int pivot = a[p];
        int left = p+1;
        int right = r;
        while (left<=right){
            while (left<=right&&a[left]<=pivot) left++;
            while (left<=right&&a[right]>pivot) right--;
            if (left<right) {
                swap(a, left, right);
            }
        }
        swap(a,p,right);
        return right;
    }


    //逆序个数：一个数列，如果左边的数大，右边的数小，就称这两个数为一个逆序对，求一个数列中有多少个逆序对
    //使用合并排序的思想，在合并的过程中，只要是右边数组被选中进入，就有逆序对，数量是左侧队伍元素的个数
    static int[] helper;
    public static void sort(int[] a){
        helper =new int[a.length];
        sort1(a,0,a.length-1);
    }

    private static void sort1(int[] a, int p, int r) {
        if (p < r){
            int mid = p + ((r - p) >> 1);
            sort1(a, p, mid); //对左侧排序
            sort1(a, mid + 1, r);//对右侧排序
            merge(a, p, mid, r);//合并
        }
    }

    static int niXu = 0;
    private static void merge(int[] a, int p, int mid, int r) {
        System.arraycopy(a,p,helper,p,r-p+1);
        int current = p;
        int left = p;
        int right = mid +1;
        while (left <= mid && right <= r){
            if (helper[left] <= helper [right]){
                a[current++] = helper[left++];
            }else {
                a[current++] = helper[right++];
                niXu += mid - left +1;
            }
        }
        if (left <= mid){
            a[current] = helper[left];
            current++;
            left++;
        }

    }


    private static void swap(int[] a, int pivot, int i) {
        int temp = a[pivot];
        a[pivot] = a[i];
        a[i]= temp;
    }
}
